package com.demo.app.sort;

import com.alibaba.druid.support.spring.stat.annotation.Stat;

/**
 * @program: couple-game
 * @description: 两个链表相加
 * @author: fbl
 * @create: 2025-05-16 14:07
 **/
public class LinkAdd {
    public static void main(String[] args) {
        Node n1 = new Node(5);
        n1.next = new Node(4);
        Node n2 = new Node(5);
        n2.next = new Node(4);
        n2.next.next = new Node(4);
        Node node = linkAdd(n1, n2);
        System.out.println(node);
    }


    private static Node linkAdd(Node n1, Node n2) {
        if (n1 == null || n2 == null) {
            return n1 == null ? n2 : n1;
        }

        // 找那条链表是长的，那条是短的
        Integer n1Length = nodeLength(n1);
        Integer n2Length = nodeLength(n2);
        Node l = n1Length >= n2Length ? n1 : n2;
        Node s = l == n1 ? n2 : n1;

        // 复制一下引用 curl curs 是操作使用的
        Node curl = l;
        Node curs = s;

        Node last = null;
        // 进位
        Integer carry = 0;
        int currentNum = 0;

        // 当短的链条没有走完时
        while (curs != null) {
            // 计算当前位置数值
            currentNum = curl.value + curs.value + carry;
            carry = currentNum / 10;
            // 将结果压入长的链表中
            curl.value = currentNum % 10;
            last = curl;
            curs = curs.next;
            curl = curl.next;
        }

        // 当长的链条没有走完时
        while (curl != null) {
            currentNum = curl.value + carry;
            carry = currentNum / 10;
            curl.value = currentNum % 10;
            last = curl;
            curl = curl.next;
        }

        // 两条链条都走完时，如果进位有值，最高位 补1
        if (carry != 0) {
            last.next = new Node(1);
        }
        return l;
    }

    private static Integer nodeLength(Node node) {
        int len = 0;
        while (node != null) {
            len++;
            node = node.next;
        }
        return len;

    }
}
